import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/29 9:41
 * @description 巧用next指针
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }

        Node leftMost = root;
        while (leftMost.left != null) {
            // 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
            Node head = leftMost;
            while (head != null) {
                // 同一个父节点的左右子节点相连
                head.left.next = head.right;
                if (head.next != null) {
                    // 不同则借助父亲的关系来连接
                    head.right.next = head.next.left;
                }
                // 指针同层后移
                head = head.next;
            }
            // 去下一层的最左节点
            leftMost = leftMost.left;
        }
        return root;
    }
}
